package sortieren;

/**Dieser Sortieralgorithmus arbeitet nicht mit den Grundoperationen get und swap.
 * 
 * @author gadmin
 */
public class MergeSort{
  int[] werte;

  public MergeSort(int[] werte){this.werte=werte;}

  public void run(){
    werte=sortiere(werte);
  }

  /**Vereinigt zwei aufeinander folgende Teile eines Arrays, die schon
   * aufsteigend sortiert sind, in einem anderen Array so, dass dieses
   * ebenfalls sortiert ist.
   * 
   * @param vorher das Array mit den beiden aufsteigend sortierten Teilen
   *   die direkt aufeinanderfolgend vorliegen.
   * @param aktaa Startindex des unteren sortierten Teils
   * @param len Länge des unteren sortierten Teils. Der obere Teil muss
   *   entweder ebenso lang sein, oder das Ende des Arrays einschließen.
   * @param nachher das ebenso große Array, in dem dann die beiden sortierten
   *   Teile als ein gesamt sortierter Abschnitt vorliegen.
   */
  public static void merge(int[] vorher, int aktaa, int len, int[] nachher){
    int aaend,aktbb,bbend;
    aktbb=aaend=aktaa+len; bbend=aktbb+len;
    if(bbend>vorher.length) bbend=vorher.length;

    for(int aktcc=aktaa; aktcc<bbend; aktcc++)
      nachher[aktcc]=
        aktbb>=bbend||(aktaa<aaend&&vorher[aktaa]<vorher[aktbb])?
        vorher[aktaa++]:vorher[aktbb++];
  }

  /**Gibt ein Array mit dem gleichen Inhalt zurück, jedoch aufsteigend sortiert.
   * Das ursprüngliche Array wird aus Platzgründen bei der Arbeit verwendet und
   * dabei verändert!
   * 
   * @param v das zu sortierende Array.
   * @return ein Array mit den gleichen Zahlen, aber aufsteigend sortiert.
   */
  public static int[] sortiere(int[] v){
    int[] w=new int[v.length];//Hilfsarray der gleichen Größe
    int len=1;
    while(len<v.length){
      for(int i=0; i<v.length; i+=2*len)
        merge(v, i, len, w);
      int[] h=v; v=w; w=h;//vertauschen der Arrays
      len*=2;
    }
    return v;
  }

  public static void main(String[] args){
    int len;
    len=args.length>0?Integer.parseInt(args[0]):20;
    int[] unsortiert=new int[len];
    for(int i=0; i<len; ++i)
      unsortiert[i]=(int)(Math.random()*10*len);
    int[] sortiert=sortiere(unsortiert);
    for(int i=0; i<sortiert.length; i++) System.out.print(sortiert[i]+" ");
    System.out.println();
  }
}
